# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
from typing import Optional

from python.mypackage import ListNode


class Solution:
    """
    方法：反转链表中每k个节点的顺序

    Args:
        head: 链表头节点
        k: 每k个节点反转一次

    Returns:
        反转后的链表头节点

    Time: O(N) - 需要遍历一次链表

    Space: O(1) - 只使用常数额外空间
    """
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        def reverse(head: ListNode) -> ListNode:
            pre = None
            cur = head
            while cur:
                next = cur.next
                cur.next = pre
                pre = cur
                cur = next
            return pre


        dummy = ListNode(next = head)
        prev = dummy
        while True:
            end = prev
            # 检查剩余节点是否够k个节点
            for _ in range(k):
                end = end.next
                if not end:
                    return dummy.next
            
            start = prev.next
            next_seg = end.next

            # 断开当前段，准备翻转
            end.next= None
            # 翻转当前段，并连接到prev
            prev.next = reverse(start)

            # 重新连接翻转后的子链表
            start.next = next_seg
            # 更新prev
            prev = start
    

    """
    方法：反转链表中每k个节点的顺序

    Args:
        head: 链表头节点
        k: 每k个节点反转一次

    Returns:
        反转后的链表头节点

    Time: O(N) - 需要遍历一次链表

    Space: O(1) - 只使用常数额外空间
    """
    def reverseKGroup1(self, head, k):
        """
        :type head: Optional[ListNode]
        :type k: int
        :rtype: Optional[ListNode]
        """
        dummy = ListNode(0)
        # Points to the predecessor node of the current sub-linked list to be reversed.
        # 指向当前待翻转子链表的前驱节点
        dummy.next = head
        # The head node of the current linked list to be reversed
        # 当前待翻转子链表的头节点
        prev = dummy
        cur = head
        while cur:
            tail = cur
            count = 0
            # Check if there are enough k nodes remaining.
            # 检查剩余节点是否足够k个
            while tail and count < k:
                tail = tail.next
                count += 1
            if count < k:
                # Directly connect the remaining part that is less than k.
                # 直接连接剩余不足k的部分
                prev.next = cur
                break
            # Reverse the current k nodes
            new_head, new_tail = self.reverse1(cur, k)
            # Connect the front node to the new head.
            prev.next = new_head # 将前驱节点连接到新头
            # Update the leading node to the new trailing node.
            prev = new_tail # 更新前驱节点为新的尾节点
            # Processing the remaining linked list
            cur = tail
        return dummy.next
        
    def reverse1(self, head, k):
        cur, prev = head, None
        for _ in range(k):
            next = cur.next
            cur.next = prev
            prev = cur
            cur = next
        # After flipping, the head is prev and the tail is head (because head has become the tail).
        return prev, head